home *** CD-ROM | disk | FTP | other *** search
/ FishMarket 1.0 / FishMarket v1.0.iso / fishies / 176-200 / disk_188 / fastgro / readme < prev    next >
Text File  |  1992-05-06  |  7KB  |  163 lines
  1.  
  2.                 FastGro 1.0
  3.  
  4.             Copyright (c) 1989  Doug Houck
  5.  
  6. PUBLIC-DOMAIN-NOTICE-PUBLIC-DOMAIN-NOTICE-PUBLIC-DOMAIN-NOTICE-PUBLIC-DOMAIN
  7. P                                       N
  8. P    This program has been placed in the public domain, and so may       N
  9. P    be copied by anyone for any purpose whatsoever.  Enjoy!           N
  10. P                                       N
  11. PUBLIC-DOMAIN-NOTICE-PUBLIC-DOMAIN-NOTICE-PUBLIC-DOMAIN-NOTICE-PUBLIC-DOMAIN
  12.  
  13.  
  14. WHAT DOES IT DO?
  15.  
  16.     FastGro is a fractal program, simulating Diffusion-Limited
  17. Aggregation (DLA).  It was inspired by a column in Scientific American,
  18. (Computer Recreations, December 1988) which described various 
  19. implementations of DLA.  The program was called SLO GRO, and took about 4
  20. to 5 hours to run.  FastGro will do the same thing, only in 4 to 5 minutes!
  21.  
  22.     To quote A. K. Dewdney, the author of the inspiring column,
  23. "It all starts when SLO GRO places a single particle at the center of the
  24. computer screen.  A particle is then set on a random walk from a random
  25. point on a large circle centered on the initial particle.  After a long
  26. and arduous journey the particle happens on the stationary particle and
  27. stops.  As soon as that happens SLO GRO will dispatch another particle
  28. on a similar journey from another random point on the circle.  Particle
  29. after particle collects at the site of the original one and a strange 
  30. shape emerges within the circle:  a treelike growth with oddly twisted
  31. branches and twigs.  The shape results from a tendency of a randomly
  32. walking particle to run into an outer part of the crowd long before it
  33. encounters a cohort much deeper in the crowd; twigs are more likely to
  34. grow from branches than from the core, so to speak."
  35.  
  36. WHAT THE PROMPTS MEAN
  37.  
  38.     FastGro needs three pieces of information: the size of the
  39. cirle, the number of particles, and how often to change colors.
  40. The acceptable range is given in parentheses (low..high), and the
  41. default is in [brackets].
  42.  
  43.     The RADIUS defines the maximum size of the fractal.  Of course,
  44. smaller ones take less time, whereas the largest take about an hour.
  45. If you have a PAL screen, or use MoreRows, the radius can be bigger.
  46. Note that a 16 color hires screen is used, so hiding it behind a lo-res
  47. screen will speed up the drawing somewhat.
  48.  
  49.     The fractal may be stopped after a given number of PARTICLES.
  50. If too large a number is given, it will outline the bounding circle.
  51. You may stop the drawing at any time by clicking on the drawing screen.
  52.  
  53.     You may CHANGE COLOR AFTER a certain number of particles have
  54. aggregated.  A small number will give a mottled effect, while larger 
  55. numbers will give a banding effect, showing the order in which the
  56. points were added.
  57.  
  58. FURTHER READING
  59.  
  60.    "Random walks that lead to fractal crowds," A. K. Dewdney in Scientific
  61.     American, Vol. 259, No. 6, pages 88-91; December, 1988
  62.  
  63.    "Fractal Growth," Leonard M. Sander in Scientific American, Vol. 256,
  64.     No. 1, pages 82-88; January, 1987
  65.  
  66.  
  67. OPTIMIZATION & IMPLEMENTATION
  68.  
  69.     The rest of this ReadMe is technical information for those who
  70. would like to know how this program was optimized.
  71.  
  72.     Calculation of Random Number for Direction
  73.  
  74.     BEFORE    direction = random
  75.  
  76.     AFTER    direction = random_array[index]
  77.         index = index + 1
  78.  
  79.     The part of the program that does the random walk takes most of
  80. the time, so it was there that I concentrated my efforts.  A random number
  81. is needed for every step of the particle's journey, and since generating
  82. random numbers takes time, I simply generated an array of random numbers
  83. when initializing, and thereafter simply scan through the array to get
  84. the required direction.  Generating the numbers is what takes the thirty
  85. seconds at the beginning.
  86.  
  87.     True, the numbers read from the array are not truly random.
  88. But were they ever?  Computer-generated random numbers are still
  89. pseudo-random, no matter how many convolutions you go through.  The $64k 
  90. question is, "Is it random enough for our purposes?"  In this case, yes.
  91. I use a large array (about 50K), and XOR each byte as I read it, which
  92. seems to mix things up enough.
  93.  
  94.     Calculation of Starting Points For Particles
  95.  
  96.     BEFORE    angle = random * 360
  97.         x = radius * cosine(angle) + x_offset
  98.         y = radius * sine(angle) + y_offset
  99.  
  100.     AFTER    index = random * NumberOfStartLocations
  101.         x = start[index].x
  102.         y = start[index].y
  103.  
  104.  
  105.     Each particle must be launched from a random point on the edge
  106. of the circle.  Rather than calculating the x,y coordinates from a 
  107. random angle while running, I have precalculated the coordinates for 
  108. reasonable number of points around the circle, and stored those in an
  109. array.  To get the starting point for a new particle, I simply get a
  110. random index into the array, and recall those points.  This saves doing
  111. trigonometry while running.
  112.  
  113.     Calculation of Distance from Center
  114.  
  115.     BEFORE    distx = x - x_offset
  116.         disty = y - y_offset
  117.         DistanceSquared = distx*distx + disty*disty
  118.  
  119.     AFTER    if border[x,y]
  120.  
  121.     Some particles might wander out of the circle.  Those should
  122. be abandoned, and new particles selected.  But how does one determine
  123. if a particle wanders out?  Determining the distance from the center
  124. of the circle requires a multiplication - much too slow for us.
  125. Instead, I create a two-dimensional array of bits, with bits set for
  126. those points corresponding to the edge of the circle.  So, to test
  127. for the edge of the circle merely requires testing a bit.  In effect, 
  128. I put a fence of bits around the working area.
  129.  
  130.     Calculation of Particle Hit
  131.  
  132.     BEFORE    if particle[x+1,y] <> 0
  133.         or particle[x,y+1] <> 0
  134.         or particle[x-1,y] <> 0
  135.         or particle[x,y-1] <> 0
  136.  
  137.     AFTER    SetSurroundingBits( x, y )
  138.         ...
  139.         if particle[x,y]
  140.  
  141.     To detect when a particle hits a stationary particle, I use another 
  142. two-dimensional array, one bit for each pixel on the screen.  Each time I
  143. set a pixel on the screen, I do the same in my array, and also set the bits
  144. surrounding it.  To detect if I am next to a particle on the screen, I check
  145. only the bit I am on in my array.  If it is set, I am near a particle.
  146. This is analogous to running a boat near the shore.  When you start to hang
  147. up on the sand, you know the shoreline is near.  This is much faster than
  148. checking all adjacent points at each step.
  149.  
  150.     The two-dimensional bit arrays are set up with a one-dimensional
  151. array of pointers to the rows.  To get to a given coordinate requires
  152. only a lookup in the pointer array, then adding an offset.  
  153.  
  154.     The routine that does the actual random walk is coded in assembly
  155. language, so as to register-optimize it.
  156.  
  157. TRADEOFFS
  158.  
  159.     Of course, optimizing for speed involves the usual tradeoff
  160. with space.  I use approximately 120K for arrays - space which may not
  161. be available in lesser machines or languages.  Total memory consumption,
  162. including code and display screen, amounts to about 300k.  
  163.